1. Field of the Invention
The present invention relates to solving frequency, frequency distribution or sequence matching and comparison problems, and more particularly, to solving frequency, frequency distribution and sequence matching and comparison problems in which description of information can be represented as sequences of symbols.
2. Background Art
The following discussion of the background of the invention is merely provided to aid the reader in understanding the invention and is not admitted to describe or constitute prior art to the present invention.
Nearly all technical fields have problems involving the representation and analysis of frequencies, frequency distributions, waveforms, signal attributes or sequences. When computational devices including hardware or software are used for the analysis or control of frequencies, frequency distributions, waveforms, signal attributes or sequences, symbols (this includes pattern and pattern recognition features) are mapped to each element or sub-element of the frequency, frequency distribution, waveform, signal attribute or sequence, thereby forming a sequence of symbols that can be either inverted back to the original frequency, frequency distribution, waveform, signal attribute or sequence or used for detection, recognition, characterization, identification or description of frequency, frequency distribution, waveform, signal attribute, sequence element or sequence.
Conventional algorithms have utilized various techniques for the identification of the number of times a symbol occurs in a symbol sequence forming a symbol frequency spectrum. An unknown symbol frequency spectrum is compared to the symbol frequency spectrum obtained by such conventional algorithms, in various applications such as modal analysis of vibrations or rotational equipment, voice recognition and natural language recognition.
In many practical applications, the symbol sequences representing frequencies, frequency distributions, waveforms, signal attributes or sequences to be matched may have regions or embedded sections with full or partial symbol sequence overlaps or may have missing or extra symbols or symbol sequence elements within one or both of their representative symbol sequences. Furthermore, the sets of symbols representing each frequency, frequency distribution, waveform, signal attribute or sequence or their sub-frequency, sub-frequency distribution, sub-waveform, signal sub-attribute or subsequence may have dissimilar elements in whole or in part.
The frequency, frequency distribution, waveform, signal attribute or sequence features to be correlated are distances, distance distributions or sets of distance distributions in the frequency, frequency distribution, waveform, signal attribute or sequence which must be discovered, detected, recognized, identified or correlated. Furthermore, in many situations, symbols in such a symbol description of frequency, frequency distribution, waveform, signal attribute or sequence typically have no known meta-meaning to allow the use of a priori statistical or other pattern knowledge to identify the significance other than the to be discovered, detected, recognized, identified or correlated frequency, frequency distribution, waveform, signal attribute or sequence themselves. A whole but unknown frequency, frequency distribution, waveform, signal attribute or sequence may be assembled from frequency, frequency distribution, waveform, signal attribute or sequence fragments which may or may not include errors in the frequency, frequency distribution, waveform, signal attribute or sequence fragments.
An unknown frequency, frequency distribution, waveform, signal attribute or sequence being assembled from fragments may have repetitive symbol sequence or symbol subsequence patterns that require recognition and may create ambiguity in assembly processes. Such ambiguity results in many types of assembly errors. Such errors may occur during the assembly of a frequency description, frequency distribution, waveform, signal attribute or sequence of wrong length due to the miss-mapping of two copies of a repeating pattern or group of repeating sub-patterns which were in different places in an unknown symbol sequence to the same position in the assembled symbol sequence. Furthermore, waveform, signal attribute or sequences may have features and feature relationships that need be discovered, indexed, classified, or correlated and then applied to the evaluation of other waveform, signal attribute or sequences.
Conventional algorithms for these types of activities usually involve the evaluation of heuristic statements or iterative or recursive searching, pattern detection, matching, recognition, identification, or correlation algorithms that can be combinatorially explosive processes, thereby requiring massive numbers of CPU cycles and huge memory or storage capacity to accomplish very simple problems.
The previously mentioned combinatorial explosion occurs because finding a specific leaf at the end of a sequence of branches from the trunk of a tree without some prior knowledge of where the right leaf may be, may require that every possible combination of trunk-(branch-sequence)-leaf be followed before the path to the right leaf is found.
In many scientific, engineering and commercial applications, the presence of ambiguity and errors makes the results unreliable, unverifiable, or makes algorithms themselves unstable or inapplicable. Efforts to mitigate these problems have centered on the restriction of the scope of heuristic evaluation and pattern algorithms by building a fixed classification structure and working from a proposed answer (the leaf) back to the original waveform, signal attribute or sequence expression (the trunk). This approach is called “backwards chaining.”
This approach works where the whole field of possible patterns and relationships has been exhaustively and mathematically completely defined (you can backward chain from the right leaf to the trunk if the right leaf is not part of the model). If any element is missing, it cannot be evaluated or returned by execution of the pattern algorithms. This problem is known as the “frame problem” that causes execution errors or failure of algorithms to satisfy their intended function. One result is that many software algorithms that have been developed are found to be unusable or impractical in many applications.
The current state of the art typically involves strategies for limiting the effect or scope of these combinatorially explosive behaviors by the development of vastly more powerful computational platforms, ever more expensive system architectures and configurations, and restriction of software algorithms to simple problems or projects which can afford the time and cost of use.